\\M0BASL30;\M1BASI30;\F0\.
LISP Functions and Programs for Game Playing


\J	These  programs comprise  three pairs  of  functions and  the
common program RECTIFY with its satellites COMMONTAIL and COMMONHEAD.
The    pairs    are    (VALMAX,VALMIN),    (LINEMAX,LINEMIN),     and
(TREEMAX,TREEMIN).   The programs  of each pair  call each  other and
differ  only in that  one is for  a position in  which the maximizing
player is to move and the other is for when the minimizer is to move.
VALMAX and  VALMIN give  the value of  the game, LINEMAX  and LINEMIN
give the value and the  main line of play,  i.e. what will happen  if
both players  use their best  moves, and TREEMAX  and TREEMIN  give a
proof  tree that  the  game has  the value  found.   This  proof tree
consists of those positions that  would be examined if the moves  had
been looked at in the best order.

	Positions are represented to these  functions by the sequence
of  moves leading to them  from the beginning of  the game in reverse
order.  This  is economical of storage,  because many positions  with
the  same  initial  segment  can   be  represented  as  merging  list
structures.  The particular game being played is embodied in the functions
SUCCESSORS, TER, and IMVAL which give the successor positions of a position,
tell whether the postion is terminal, and if so give its value.
RECTIFY is a the identity function used for a side effect.  The idea
is that it is usually convenient in computing the successors, etc.
to represent positions
other than as a list of moves, e.g. as a set of tables.  Associated
with a position is a set of tables and a list of moves leading to
the position represented in the tables.  VALMAX etc. get new positions
by \F1cons\F0ing moves onto old positions and by \F1cdr\F0ing to
revert.  RECTIFY applied to the list representing a position returns
the same list but readjusts the tables to correspond to the postion
given by the list.  In doing this it uses COMMONTAIL to determine
what moves to take back and game dependent programs UPDATE(move)
and REVERT in order to make the adjustments.

	The purpose of these programs is to illustrate the recursive
structure of this kind of calculation in a way independent of the
particular game.  Some additional heuristics, such as the \F1killer\F0
heuristic can also be put in this game independent form.

	The functions SUCCESSORS, TER, IMVAL, UPDATE, and REVERT are
available in files for the game of tictactoe.
\.